class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        const int n = matrix.size();
        const int m = matrix[0].size();
        int dp[n][m];
        memset(dp, 0, sizeof(dp));

        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                if(i == 0 || j == 0)
                    dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
                else
                {
                    if(matrix[i][j] == '0')
                        dp[i][j] = 0;
                    else
                        dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                }
                ans = max(dp[i][j], ans);
            }
        }

        return ans * ans;
    }
};
